//
// Created by jerry on 2024/6/5.
//

#include "sort.h"

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void showNode(HeapType heap, int index, int depth)
{
    int i, left = depth * 2, right = index * 2 + 1;

    for (i = 0; i < depth; i++)
        printf("  ");
    printf("%d\n", heap.r[index]);
    if (left < heap.length)
    {
        showNode(heap, left, depth + 1);
    }
    if (right < heap.length)
        showNode(heap, right, depth + 1);
}
void showHeap(HeapType heap)
{
    showNode(heap, 1, 0);
}
#ifdef ORIGINAL
void HeapAdjust(HeapType *list, int s, int m) {
    int j;
    list->r[0] = list->r[s];
    int parent;
    for (j = 2 * s; j <= m; j *= 2) {
        parent = j / 2;
        if (j < m && list->r[j] < list->r[j + 1]) {
            // left < right
            j++;
        }
        if (list->r[parent] < list->r[j]) {
            // stored_min < max in subtree
            swap(list->r+parent, list->r + j);
            s = j;
        }
    }
    list->r[s] = list->r[0];
    showList(*list);
}
void HeapSort(HeapType *h)
{
    int i;
    for (i = h->length / 2; i > 0; i--)
        HeapAdjust(h, i, h->length);
    for (i = h->length; i > 1; i--)
    {
        swap(h->r + 1, h->r + i);
        HeapAdjust(h, 1, i - 1);
#ifdef DEBUG
        // showHeap(*h);
        showList(*h);
#endif
    }
}
#elif defined TEST

void HeapSort(HeapType *list)
{

}
#else

// 堆调整函数，维护堆性质
void heapify(SqList *L, int n, int i)
{
    int largest = i;       // 初始化为根节点
    int left = 2 * i + 1;  // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点存在且大于根节点
    if (left < n && L->r[left] > L->r[largest])
        largest = left;

    // 如果右子节点存在且大于当前最大值
    if (right < n && L->r[right] > L->r[largest])
        largest = right;

    // 如果最大值不是根节点
    if (largest != i)
    {
        swap(&L->r[i], &L->r[largest]); // 交换
        heapify(L, n, largest);         // 递归地对受影响的子树进行堆调整
    }
}

// 主函数，执行堆排序
void HeapSort(SqList *L)
{
    int n = L->length;

    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(L, n, i);

#ifdef DEBUG
    printf("构建最大堆后: ");
    showList(*L);
#endif

    // 一个一个地取出元素
    for (int i = n - 1; i > 0; i--)
    {
        swap(&L->r[0], &L->r[i]); // 交换
        heapify(L, i, 0);         // 调整堆

#ifdef DEBUG
        printf("交换并调整后的堆: ");
        showList(*L);
#endif
    }
}
#endif